package com.yuan.algorithms.arithmetic_1;

/*
 假设有X,Y,Z三个塔座，初始时有n个大小不一的盘子按照从小到大的次序放在塔座X上。
 现在要求将塔座X上的所有盘子移动到塔座Z上并保持原来的顺序，在移动的过程中满足以下要求：
 在塔座之间一次只能移动一个盘子，并且任何时候大盘子都不能放在小盘子上。
 
 -------------------------------------------------------
 
 算法分析：若只有一个盘子，则不需要过渡塔座，直接把它放到目的塔座即可。
如果有多个盘子，则需要将塔座X上的1~n-1个盘子使用Z作为过渡塔座放到塔座Y上，然后将第n个盘子（最后一个盘子）
放到塔座Z，最后将塔座Y上的n-1个盘子使用塔座X作为过渡放到塔座Z。
 */

import java.util.Scanner;

public class 递归_汉诺塔 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			hanio(n, 'x', 'y', 'z');
		}

	}

	private static void hanio(int n, char x, char y, char z) {
		if (n == 1) {
			move(x, n, z);
		} else {
			hanio(n - 1, x, z, y);
			move(x, n, z);
			hanio(n - 1, y, x, z);
		}

	}

	private static void move(char x, int n, char y) {
		System.out.println("Move " + n + " from " + x + " to " + y);

	}

}
